// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package runtime

import (
	"runtime/internal/atomic"
	"runtime/internal/sys"
	"unsafe"
)

const (
	// 对于时间直方图类型，我们使用HDR直方图。
	// 值仅基于最
	// 有效设置位放置在超级存储桶中。因此，超级铲斗的大小为2次方。
	// 然后根据
	// 下一次HistSubBucketBits最高有效位的值将值放入子存储桶中。因此，
	// 子桶在超级桶中是线性的。
	// 
	// 因此，子桶数（timehistnumsubbucket）
	// 定义了错误。此错误可计算为
	// 1/TimeHistNumSubbucket*100%。例如，对于16个子存储桶
	// 每个超级存储桶，误差约为6%。
	// 
	// 超级存储桶的数量（TimeHistNumSuperBucket），另一方面，
	// 定义了范围。为了给子bucket预留空间，
	// 位timeHistSubBucketBits是
	// 超级bucket考虑的第一位，因此超级bucket索引会相应调整。ABCFDG 
	// 
	// 00110 
	// /^----
	// │  ^ 
	// │  └---- 最低4位->子存储桶6 
	// └------- 第4位未设置->超级存储桶0 
	// 
	// 10110 
	// /^----
	// │  ^ 
	// │  └---- 下4位->子存储桶6 
	// └------- 第4位设置->超级桶1 
	// 100010 
	// /^-^
	// │  ^ └-- 忽略低位
	// │  └---- 下4位->子存储桶1 
	// └------- 设置第5位->超级存储桶2 
	// 
	// 按照此模式，存储桶45将设置第48位。我们没有用于更高值的存储桶，因此最高的子存储桶将包含2^48-1纳秒或大约3天的值。此范围为
	// 足以处理运行时生成的持续时间。
	timeHistSubBucketBits   = 4
	timeHistNumSubBuckets   = 1 << timeHistSubBucketBits
	timeHistNumSuperBuckets = 45
	timeHistTotalBuckets    = timeHistNumSuperBuckets*timeHistNumSubBuckets + 1
)

// 时间直方图表示持续时间在
// 纳秒中的分布。
// 
// 直方图的精度和范围由
// timeHistSubBucketBits和timeHistNumSuperBuckets常量定义。
// 
// 这是一个HDR直方图，具有指数分布的
// 桶和线性分布的子桶。
// 
// 直方图中的计数以原子方式更新，因此安全
// 可同时使用。以原子方式读取所有值
// 也是安全的。
type timeHistogram struct {
	counts [timeHistNumSuperBuckets * timeHistNumSubBuckets]uint64

	// 持续时间为负数时的下溢计数
	// 样本。由于时间在某些平台上是如何工作的，因此可以测量负持续时间。我们可以忽略它们，但无论如何我们都要记录它们，因为最好有一些
	// 信号表明它正在发生，而不仅仅是缺少样本。
	underflow uint64
}

// 记录将给定的持续时间添加到分发中。
// 
// 不允许抢占和堆栈增长，因为此函数
// 可能在敏感位置运行。
// go:nosplit 
func (h *timeHistogram) record(duration int64) {
	if duration < 0 {
		atomic.Xadd64(&h.underflow, 1)
		return
	}
	// 指数桶的索引就是最高设置位的索引
	// 调整为我们
	// 用于子桶的位数。请注意，它是timeHistSubBucketsBits-1 
	// 因为我们使用第0个bucket来保存<timehistnumsubbucket的值。
	var superBucket, subBucket uint
	if duration >= timeHistNumSubBuckets {
		// 此时，我们知道持续时间值将始终为
		// 至少为timeHistSubBucketsBits长。
		superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits
		if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) {
			// 我们得到的桶索引比我们支持的要大，所以
			// 将此计数包含在最高桶中，扩展到
			// 无穷大。
			superBucket = timeHistNumSuperBuckets - 1
			subBucket = timeHistNumSubBuckets - 1
		} else {
			// 线性子Bucket索引就是最高位后的timeHistSubBucketsBits 
			// 位。要提取该值，请向下移动
			// 持续时间，使顶部位和下一位
			// 保持不变，然后提取索引。
			subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets)
		}
	} else {
		subBucket = uint(duration)
	}
	atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1)
}

const (
	fInf    = 0x7FF0000000000000
	fNegInf = 0xFFF0000000000000
)

func float64Inf() float64 {
	inf := uint64(fInf)
	return *(*float64)(unsafe.Pointer(&inf))
}

func float64NegInf() float64 {
	inf := uint64(fNegInf)
	return *(*float64)(unsafe.Pointer(&inf))
}

// 时间直方图为
// 时间直方图生成一个边界切片。这些边界以秒表示，而不是像时间直方图表示持续时间那样的纳秒。
func timeHistogramMetricsBuckets() []float64 {
	b := make([]float64, timeHistTotalBuckets+1)
	b[0] = float64NegInf()
	for i := 0; i < timeHistNumSuperBuckets; i++ {
		superBucketMin := uint64(0)
		// 第一个非负桶的最小值（含）为0。
		if i > 0 {
			// 第二个存储桶的最小值为
			// 1<<timeHistSubBucketBits，表示所有
			// 子存储桶都由下一个timeHistSubBucketBits 
			// 位表示。
			// 此后，我们每次向上移动1，因此我们可以将
			// 此模式表示为（i-1）+timeHistSubBucketBits。
			superBucketMin = uint64(1) << uint(i-1+timeHistSubBucketBits)
		}
		// subBucketShift是我们需要移动子bucket的量
		// 索引以将其与bucketMin组合。
		subBucketShift := uint(0)
		if i > 1 {
			// 前两个超级存储桶与整数的关系是精确的，因此我们永远不必移动子存储桶索引。此后，
			// 我们在每个后续桶中上移1。
			subBucketShift = uint(i - 2)
		}
		for j := 0; j < timeHistNumSubBuckets; j++ {
			// j为子桶索引。通过将索引移动到
			// 位置，并结合桶最小值，我们获得该
			// 子桶的最小值。
			subBucketMin := superBucketMin + (uint64(j) << subBucketShift)

			// 将以纳秒为单位的subBucketMin值转换为浮点64秒值。
			// 这些值都可以用float64表示。
			b[i*timeHistNumSubBuckets+j+1] = float64(subBucketMin) / 1e9
		}
	}
	b[len(b)-1] = float64Inf()
	return b
}
